package cg.studio.practise;

import java.util.Arrays;

/**
 * ref: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
 * 
 * Say you have an array for which the ith element is the price of a given stock on day i.
 * Design an algorithm to find the maximum profit. You may complete at most k transactions.
 * Note:
 * You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
 * 
 * @author Bright Chen
 *
 */
public class Stock
{
  //keep profits sorted from small, so minProfitIndex point to the first one when profits is full.
  private int[] profits = null;
  private int minProfitIndex = profits.length-1;
  
  /**
   * Buy at minimal price and sell at max price in a certain period
   * @param k
   * @param prices
   * @return
   */
  public int maxProfit(int k, int[] prices) 
  {
    //keep the max k profits
    profits = new int[k];
    
    int prePrice = prices[0]; 
    int maxPrice = prePrice;
    int minPrice = prePrice;
    Boolean goingUp = null;   //null means flat
    boolean trendChanged = false;
    for( int index=1; index<prices.length; ++index )
    {
      if( prices[index] > prePrice )
      {
        //go up;
        trendChanged = ( goingUp != null && !goingUp );
        if( trendChanged )
        {
          minPrice = prePrice;
        }
      }
      else if( prices[index] < prePrice )
      {
        //go down;
        trendChanged = ( goingUp != null && goingUp );
        if( trendChanged )
        {
          maxPrice = prePrice;
          addProfit( profits, maxPrice-minPrice );
        }
         
      }
      // else; not change the trend
      
    }
    
    int totalProfit = 0;
    for( int profit : profits )
      totalProfit += profit;
    
    return totalProfit;
  }
  
  protected void addProfit( int[] profits, int profit )
  {
   
    if( minProfitIndex != 0 )
    {
      //not full. just keep it
      profits[ minProfitIndex ] = profit;
      --minProfitIndex;
      if( minProfitIndex == 0 )
      {
        //sort
        Arrays.sort( profits );
      }
    }
    else
    {
      //should move it in order to insert
      if( profit <= profits[0] )
        return;
      int index =1;
      for( ; index<profits.length; ++index )
      {
        if( profits[index] >= profit )
          break;
        
        profits[index-1] = profits[index];
      }
      profits[index-1] = profit;
    }
  }
}
